#include <stdio.h>
#include <string.h>
#include "common.h"
#include "euler.h"


Stack(int)
Array(int)



/*
 	Element cyrkularnej listy dwukerunkowej z wezlami blizniaczymi
*/
struct Link_ {
	struct Link_	*prev, *next, *twin;
	int				i;
};
typedef struct Link_ Link;


/**
	Tworzenie nowego elementu
*/
Link* Link_new(int i) {
	Link* res = new(Link, 1);
	res->prev = res->next = res;
	res->twin = null;
	res->i = i;
	return res;
}

/**
	Doczepienie elementu 'other' do elementu 'link'
*/
void Link_attach(Link* link, Link* other) {
	other->next = link->next;
	other->next->prev = other;
	other->prev = link;
	link->next = other;
}

/**
	Wylaczenie elementu 'link' z cyklu
*/
void Link_detach(Link* link) {
	Link* tw = link->twin;
	link->prev->next = link->next;
	link->next->prev = link->prev;
	link->prev = link->next = link;
	if (link->twin != null) {
		link->twin = null;
		Link_detach(tw);
	}
}


/**
	Wylaczenie elementu 'link' z cyklu oraz jego usuniecie
*/
void Link_delete(Link* link) {
	Link* tw = link->twin;
	Link_detach(link);
	Link_detach(tw);
	free(link);
	free(tw);
}


/**
	Graf nieskierowany, niewazony, zbudowany z list cyrkularnych.
	Usuwanie krawedzi w czasie O(1)
	Dodawanie krawedzie w czasie O(1)
*/
typedef struct {
	Link*	links;
} LGraph;


void findEulerCycle(Graph graph, intArray* res) {
	LGraph	lgraph;
	intStack	stack;
	int		curVertex, i, j;
	Link		*l1, *l2;
	bool		moreNeighbors;

	stack = intStack_new();
	*res = intArray_new();

	// inicjalizuj lgraph
	lgraph.links = new(Link, graph.numNodes);
	for (i = 0; i < graph.numNodes; ++i) {
		lgraph.links[i].prev = lgraph.links[i].next = &lgraph.links[i];
		lgraph.links[i].twin = null;
	}

	// buduj lgraph
	for (i = 0; i < graph.numNodes; ++i) {
		// nie lacz wierzcholka do samego siebie, uwazaj na bledy
		if (graph.prev[i] == i || graph.prev[i] == -1) continue;
		
		for (j = 0; j < 2; ++j) {
			l1 = Link_new(graph.prev[i]);
			l2 = Link_new(i);
			l1->twin = l2;
			l2->twin = l1;
			assert(l1->i != l2->i);

			// polacz wierzcholki wg pola 'prev'
			Link_attach(&lgraph.links[i], l1);
			Link_attach(&lgraph.links[graph.prev[i]], l2);
		}
	}


	// dowolne zrodlo
	curVertex = 0;


	do {
	continueSkipCondition:
		assert (curVertex < graph.numNodes);

		// czy obecny wierzcholek ma sasiadow ?
		moreNeighbors = lgraph.links[curVertex].next != &lgraph.links[curVertex];

		// jesli nie, dodaj go do cyklu eulera i kontynuuj z wierzcholkiem z gory stosu
		if (!moreNeighbors) {
			intArray_append(res, curVertex);
			/*printf("stuck in %d. to circuit\n", curVertex);*/

			// ... jesli jest cos na stosie
			if (!intStack_empty(&stack)) {
				curVertex = intStack_top(&stack);
				intStack_pop(&stack);
				goto continueSkipCondition;
			} else {
				// nie ma sasiadow i stos jest pusty, koncz.
				break;
			}
		}


		// dowolny sasiad
		l1 = lgraph.links[curVertex].next;
		assert (l1 != &lgraph.links[curVertex]);

		/*printf("going from %d to %d\n", curVertex, l1->i);*/

		// dodajemy go do stosu ...
		intStack_push(&stack, curVertex);

		// ... i przechodzimy do niego ...
		curVertex = l1->i;

		// ... usuwajac przebiegana krawedz
		Link_delete(l1);

		/*printf("conns:");
		for (l1 = lgraph.links[curVertex].next; l1 != &lgraph.links[curVertex]; l1=l1->next) {
			printf(" %d", l1->i);
		}
		printf("\n");*/

	} while (moreNeighbors || !intStack_empty(&stack));

	intStack_delete(&stack);
	free(lgraph.links);

	#undef moreNeighbors
}


/**
	testy dla stosu i tablic
*/

#ifdef ARRAY_STACK_TEST
int main() {
	int i;
	intStack st;
	intArray arr = intArray_new();

	intArray_append(&arr, 1);
	intArray_append(&arr, 2);
	intArray_append(&arr, 3);
	intArray_append(&arr, 4);
	intArray_append(&arr, 5);

	printf("Array length : %d, capacity: %d\n", arr.length, arr.capacity);
	assert (5 == arr.length);
	assert (8 == arr.capacity);

	for (i = 0; i < arr.length; ++i) {
		printf("%d : %d\n", i, arr.data[i]);
		assert (arr.data[i] == i+1);
	}

	intArray_delete(&arr);
	assert (0 == arr.length);
	assert (0 == arr.capacity);


	st = intStack_new();
	intStack_push(&st, 3);
	intStack_push(&st, 5);
	intStack_push(&st, 10);
	intStack_push(&st, 20);

	assert(20 == intStack_top(&st));
	intStack_pop(&st);
	assert(10 == intStack_top(&st));
	intStack_pop(&st);
	assert(5 == intStack_top(&st));
	intStack_pop(&st);
	assert(3 == intStack_top(&st));
	intStack_pop(&st);
	assert(intStack_empty(&st));

	intStack_delete(&st);

	printf("data structures tests passed!\n");

	return 0;
}
#endif  // ARRAY_STACK_TEST
